import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-07-20
 * Time: 18:21
 */
class Solution10 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int n = nums.length, m = 0, minValue = Integer.MAX_VALUE;

        for(int x : nums) {
            if(x < 0) {
                m++;
            }
            minValue = Math.min(minValue,Math.abs(x));
        }
        int ret = 0;
        if(m > k) {
            Arrays.sort(nums);
            for(int i = 0; i < k;i++) {
                ret += -nums[i];
            }
            for(int i = k; i < n; i++) {
                ret += nums[i];
            }
        }else {
            for(int x : nums) {
                ret += Math.abs(x);
            }
            if((k-m) % 2 != 0) {
                ret -= 2 * minValue;
            }
        }
        return ret;
    }
}
